Server: Netscape-Communications/1.1
Date: Wednesday, 20-Nov-96 23:24:19 GMT
Last-modified: Friday, 30-Aug-96 20:11:20 GMT
Content-length: 5025
Content-type: text/html

<HTML>
<HEAD>
<TITLE>CIS 511 Handout 1</TITLE>
<BODY><! BODY BGCOLOR = "#000000" TEXT = "#FFFFFF">
<BODY bgcolor="#FFEFDB">  <! AntiqueWhite1>
<H1><CENTER>CIS 511, Summer 1, 96 </CENTER> <P>
<center>
Introduction to the Theory of Computation
</CENTER>
<CENTER>Course Information</CENTER>
<CENTER>May 17 </CENTER></H1>
<P>
<H4>
<H2>Coordinates:</H2> Moore 223, 2:00-5:00
<P>
<H2>Instructor:</H2> <A HREF="mailto:jean@saul.cis.upenn.edu">Jean H. 
Gallier</A>, MRE 176, 8-4405, jean@saul <P>
<H2>Office Hours:</H2> 11:00-noon Monday, Wednesday, 11:00-noon, Tuesday
<P>
<H2>Teaching Assistant:</H2>
Shiann-Liang Chern, slchern@saul.cis.upenn.edu  <p>
<H2>Office Hours:</H2> Tuesday-Thursday, 2:00-4:00 <P>
<H2>Newsgroup:</H2><a href="news:upenn.cis.cis511">upenn.cis.cis511</a>
<H2>Textbook (required):</H2> <I>Introduction to Automata Theory, Languages
and Computation </I>, J.E. Hopcroft and J.D. Ullman, Addison Wesley<BR>
<BR>Also recommended:<BR>
<BR><I>Theory of Computation</I>, D. Wood, Wiley
<P>
<H2>Grades: homework assignments and take home final</H2>
<P>
<H2>  Problem Sets (3 of them) </H2>
<ul>
<li><a
    href="http://www.cis.upenn.edu/~jean/cis51196shm1.ps.Z"> Homework1 </a>
<li><a
    href="http://www.cis.upenn.edu/~jean/cis51196shm2.ps.Z"> Homework2 </a>
<li><a
    href="http://www.cis.upenn.edu/~jean/cis51196shm3.ps.Z"> Homework3 </a>
</ul>
<P>
<H2> Some Course Notes </H2>
<ul>
<li> <a
    href="http://www.cis.upenn.edu/~jean/baslang.ps.Z"> Basics of language theory,
     DFA's, the cross-product
     construction, and the subset algorithm</a>
<li><a
    href="http://www.cis.upenn.edu/~jean/dirgraph.ps.Z"> Labeled graphs </a>
<li> <a
    href="http://www.cis.upenn.edu/~jean/regexpr.ps.Z"> Regular expressions
     and the node elimination algorithm</a>
<li> <a
    href="http://www.cis.upenn.edu/~jean/nerode.ps.Z"> The Nerode-Myhill
     theorem and minimal DFA's</a>
<li> <a
    href="http://www.cis.upenn.edu/~jean/cfl1.ps.Z"> Context-free grammars,
     context-free languages, parse trees, and Ogden's Lemma</a>
<li> <a
    href="http://www.cis.upenn.edu/~jean/pda.ps.Z"> Context-free Languages
    and PDAs </a>
<li> <a
    href="http://www.cis.upenn.edu/~jean/turing1.ps.Z"> Turing machines,
     Partial Recursive Functions, r.e. sets, phrase-structure grammars</a>
</ul>
<P>
<H2>Brief description:</H2> The course provides an introduction to 
the theory of computation.  The treatment is mathematical, but the point 
of view is that of Computer Science.  Roughly speaking, the theory of 
computation consists of three overlapping subareas: (1) formal languages 
and automata; (2) computability and recursive function theory; (3) 
complexity theory.  The course will focus mostly on (1) and (2).  Applications 
of (1) to programming (and natural) language specification and 
parsing (top-down and bottom-up parsing), will be emphasized.<BR>
<P>
Topics will include:
<UL>
<LI> Basics of language theory: alphabets, strings, concatenation, 
languages, operations on languages (including Kleene *)
<LI> Deterministic finite automata (DFA's)
<LI> The cross-product construction
<LI> Nondeterministic finite automata (NFA's)
<LI> From NFA's to DFA's, the subset algorithm (Rabin and Scott)
<LI> Labeled directed graphs, NFA's and DFA's
<LI> Regular languages and regular expressions
<LI> From regular expressions to NFA's
<LI> From NFA's to regular expressions (node elimination)
<LI> Right-invariant equivalence relations
<LI> The Nerode/Myhill characterization theorem
<LI> The pumping lemma for regular languages
<LI> State equivalence, minimal DFA's
<LI> Fractals and languages (a glimpse)
<LI> Context-free grammars and context-free languages
<LI> Leftmost derivations, rightmost derivations, parse trees
<LI> The universality of leftmost derivations
<LI> Cleaning-up context-free grammars (e-rules, chain rules)
<LI> Chomsky Normal Form
<LI> Right-linear grammars and regular languages
<LI> Eliminating useless productions
<LI> Greibach Normal Form
<LI> Tree domains, Gorn trees, and parse trees
<LI> A strong pumping lemma for context-free languages: Ogden's lemma
<LI> Pushdown Automata (PDA's), instantaneous descriptions, acceptance modes
<LI> DPDA's (Deterministic PDA's) 
<LI> From context-free grammars to PDA's
<LI> From PDA's to context-free grammars
<LI> A glimpse at LR-parsing
<LI> Generalities on computability, models of computation
<LI> Turing Machines
<LI> RAM programs (flowchart and sequential form)
<LI> Primitive recursive functions
<LI> Recursive and partial recursive functions
<LI> Recursively enumerable languages and recursive languages
<LI> The equivalence of RAM computable and Turing computable functions
<LI> The equivalence of Turing computable functions and partial recursive functions
<LI> Phrase-Structure Grammars 
<LI> Type-0 Languages
<LI> Type-0 Grammars and Context-Sensitive Grammars
<LI> Monotonic Grammars and Linear-Bounded Automata
</UL>
<P>
<I>published by:
<H2><A HREF="mailto:jean@saul.cis.upenn.edu">Jean Gallier</A></H2>
</H4>
<BODY>
<HTML>

